Legendre Symbol

Motivated by Euler's criterion, the Legendre symbol is a compact notation to encompass if $a$ is a quadratic residue modulo $p$.

This definition means, by Euler's criterion, that

noting that in the new case when $a\equiv 0(\mathrm{mod}p)$ then $a^{\frac{p-1}{2}}\equiv 0(\mathrm{mod}p)$.

The Legendre symbol is multiplicative, which is very useful when computing it.